package 剑指Offer1;

public class _43二叉搜索树的后序遍历序列 {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null) return false;
        return helper(postorder,0, postorder.length-1);
    }

    public boolean helper(int[] postorder,int i,int j){
        if(i>=j) return true; //只有一个节点,无序判断正确性，返回true
        int p = i;
        while(postorder[p]<postorder[j]) p++; //先找到左子树的区间范围
        int m = p; //左子树的区间范围为[i,m-1];
        while(postorder[p]>postorder[j]) p++; //找到右子树的区间范围 [m,j-1]

        //此树是正确的后序遍历，必须 p==j 才为正确的二叉搜索树的后序遍历,递归判断左子树和右子树
        return p == j && helper(postorder,i,m-1) && helper(postorder,m,j-1);
    }
}
